//Code inspired by Glenn Fowler's sudoku solver/generator
//The original is published under the following license
		/***********************************************************************
		*               This software is part of the ast package               *
		*          Copyright (c) 2005-2009 AT&T Intellectual Property          *
		*                      and is licensed under the                       *
		*                  Common Public License, Version 1.0                  *
		*                    by AT&T Intellectual Property                     *
		*                                                                      *
		*                A copy of the License is available at                 *
		*            http://www.opensource.org/licenses/cpl1.0.txt             *
		*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
		*                                                                      *
		*              Information and Software Systems Research               *
		*                            AT&T Research                             *
		*                           Florham Park NJ                            *
		*                                                                      *
		*                 Glenn Fowler <gsf@research.att.com>                  *
		***********************************************************************/
//This is a MODIFIED version of the original code 
#include "cantables.h"


//code inspired by Glenn Fowler's <gsf@research.att.com> sudoku solver/generator 
static Canon_t* canon(unsigned char* sol)
{
	register int			b;
	register int			d;
	register int			i;
	register int			j;
	register int			k;
	register int			l;
	register int			v;

	int				a;
	int				pr;
	int				pc;

	Canon_t				test;

	static Canon_t		best;

	/* initialize the worst canonical candidate */

	a = 1;
	best.box = 0;
	for (i = 0; i < 9; i++) {
		best.map[i] = 10;
		best.row[i] = best.col[i] = i;
	}
	best.map[i] = 10;

	/* search over all boxes */

	for (b = 0; b < 18; b++) {
		for (pr = 0; pr < 6; pr++)
			for (pc = 0; pc < 6; pc++) {
				test.box = b;

				/* initialize the map */

				for (i = 0; i < 3; i++) {
					test.row[i] = tperm[pr][i];
					test.col[i] = tperm[pc][i];
				}
				for (i = 1; i <= 9; i++)
					test.map[i] = 0;
				test.map[sol[tswap[b][test.row[0]][test.col[0]]]] = 1;
				test.map[sol[tswap[b][test.row[0]][test.col[1]]]] = 2;
				test.map[sol[tswap[b][test.row[0]][test.col[2]]]] = 3;
				test.map[sol[tswap[b][test.row[1]][test.col[0]]]] = 4;
				test.map[sol[tswap[b][test.row[1]][test.col[1]]]] = 5;

				/* map value 6 and order cols 4&5&6 */

				k = 0;
				for (i = 3; i < 9; i++) {
					if (test.map[sol[tswap[b][test.row[0]][i]]] == 4) {
						l = tboxOffset[i];
						for (j = 0; j < 3; j++)
							switch (test.map[sol[tswap[b][test.row[0]][j+l]]]) {
							case 4:
								test.col[3] = j+l;
								k |= 01;
								break;
							case 5:
								test.col[4] = j+l;
								k |= 02;
								break;
							case 0:
								test.map[sol[tswap[b][test.row[0]][test.col[5]=j+l]]] = 6;
								k |= 04;
								break;
						}
						break;
					}
				}
				if (k != 7)
					goto next;

				/* map values 7&8&9 */

				for (j = 2; j < 6; j++) {
					if (!test.map[sol[tswap[b][test.row[1]][test.col[j]]]])
						test.map[sol[tswap[b][test.row[1]][test.col[j]]]] = k++;
				}

				/* check row 2 cols 3&4&5&6 */

				for (j = 2; j < 6; j++) {
					if ((d = (int)test.map[sol[tswap[b][test.row[1]][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[1]][best.col[j]]]])) {
						if (d > 0)
							goto next;
						break;
					}
				}

				/* order cols 7&8&9 */

				j = (l == 3) ? 6 : 3;
				k = j+1;
				l = j+2;
				if (test.map[sol[tswap[b][test.row[0]][j]]] > test.map[sol[tswap[b][test.row[0]][k]]]) {
					v = j; j = k; k = v;
				}
				if (test.map[sol[tswap[b][test.row[0]][j]]] > test.map[sol[tswap[b][test.row[0]][l]]]) {
					v = j; j = l; l = v;
				}
				if (test.map[sol[tswap[b][test.row[0]][k]]] > test.map[sol[tswap[b][test.row[0]][l]]]) {
					v = k; k = l; l = v;
				}
				test.col[6] = j;
				test.col[7] = k;
				test.col[8] = l;

				/* check row 2 cols 7&8&9 */

				if (!d) {
					for (j = 6; j < 9; j++) {
						if ((d = (int)test.map[sol[tswap[b][test.row[1]][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[1]][best.col[j]]]])) {
							if (d > 0)
								goto next;
							break;
						}
					}
				}

				/* check row 3 */

				if (!d) {
					for (j = 0; j < 9; j++) {
						if ((d = (int)test.map[sol[tswap[b][test.row[2]][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[2]][best.col[j]]]])) {
							if (d > 0)
								goto next;
							break;
						}
					}
				}

				/* done with the first band */

				/* order row 4 */

				v = 10;
				i = 9;
				while (--i >= 3) {
					if (test.map[sol[tswap[b][i][test.col[0]]]] < v) {
						v = test.map[sol[tswap[b][i][test.col[0]]]];
						k = i;
					}
				}

				/* check row 4 */

				if (!d) {
					for (j = 0; j < 9; j++) {
						if ((d = (int)test.map[sol[tswap[b][k][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[3]][best.col[j]]]])) {
							if (d > 0)
								goto next;
							break;
						}
					}
				}
				test.row[3] = k;

				/* order rows 5&6 */

				if (test.map[sol[tswap[b][tpart[k][0]][test.col[0]]]] < test.map[sol[tswap[b][tpart[k][1]][test.col[0]]]]) {
					test.row[4] = tpart[k][0];
					test.row[5] = tpart[k][1];
				}
				else {
					test.row[4] = tpart[k][1];
					test.row[5] = tpart[k][0];
				}

				/* check rows 5&6 */

				if (!d) {
					for (i = 4; i < 6; i++) {
						for (j = 0; j < 9; j++) {
							if ((d = (int)test.map[sol[tswap[b][test.row[i]][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[i]][best.col[j]]]])) {
								if (d > 0)
									goto next;
								i = 6;
								break;
							}
						}
					}
				}

				/* done with the second band */

				/* order row 7 */

				v = 10;
				for (i = 2; i < 5; i++) {
					if (test.map[sol[tswap[b][tpart[k][i]][test.col[0]]]] < v) {
						v = test.map[sol[tswap[b][tpart[k][i]][test.col[0]]]];
						l = tpart[k][i];
					}
				}

				/* check row 7 */

				if (!d) {
					for (j = 0; j < 9; j++) {
						if ((d = (int)test.map[sol[tswap[b][l][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[6]][best.col[j]]]])) {
							if (d > 0)
								goto next;
							break;
						}
					}
				}
				test.row[6] = l;

				/* order rows 8&9 */

				if (test.map[sol[tswap[b][tpart[l][0]][test.col[0]]]] < test.map[sol[tswap[b][tpart[l][1]][test.col[0]]]]) {
					test.row[7] = tpart[l][0];
					test.row[8] = tpart[l][1];
				}
				else {
					test.row[7] = tpart[l][1];
					test.row[8] = tpart[l][0];
				}

				/* check rows 8&9 */

				if (!d) {
					for (i = 7; i < 9; i++)
						for (j = 0; j < 9; j++)
							if ((d = (int)test.map[sol[tswap[b][test.row[i]][test.col[j]]]] - (int)best.map[sol[tswap[best.box][best.row[i]][best.col[j]]]])) {
								if (d > 0)
									goto next;
								i = 9;
								break;
							}
				}

				/* check for automorphism */

				if (d)
					a = 1;
				else {
					a++;
					goto next;
				}
				best = test;
next:
				;
			}
	}
	best.aut = a;
	return &best;
}

void rowminlex(char *in, char *out) {
	Canon_t *can;
	can = canon((unsigned char*)in);
	register int	i;
	register int	j;
	register char*	s;

	s = out;
	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
			*s++ = can->map[in[tswap[can->box][can->row[i]][can->col[j]]]];
}
